//
//  ReverseString.cpp
//  CppDemo
//
//  Created by 蒋益杰 on 16/9/8.
//  Copyright © 2016年 com.ed. All rights reserved.
//

#include "ReverseString.hpp"
#include <iostream>

void reverse(char *s, int start, int end) {
    int j = end, i = start;
    
    for (; i <= (start + (end - start) / 2); i++) {
        std::swap(s[i], s[j]);
        j--;
    }
}

void leftshift(char *s, int strlen, int num_to_shift) {
    reverse(s, 0, num_to_shift - 1);
    reverse(s, num_to_shift, strlen - 1);
    reverse(s, 0, strlen - 1);
}

#pragma mark - reverse List
RListNode* reverseList(RListNode *head) {
    RListNode *pReverseHead = NULL;
    RListNode *pNode = head;
    RListNode *pPrev = NULL;
    
    while (pNode != NULL) {
        RListNode *pNext = pNode->next;
        
        if (pNext == NULL) {
            pReverseHead = pNode;
        }
        
        pNode->next = pPrev;
        
        pPrev = pNode;
        pNode = pNext;
    }
    return pReverseHead;
}

int inversePairsCore(int *data, int *copy, int start, int end) {
    if (start == end) {
        copy[start] = data[start];
        return 0;
    }
    
    int length = (end - start) >> 1;
    int left = inversePairsCore(copy, data, start, start + length);
    int right = inversePairsCore(copy, data, start + length + 1, end);
    
    int i = start + length;
    int j = end;
    int indexCopy = end;
    
    int count = 0;
    
    while (i >= start && j >= start + length + 1) {
        if (data[i] > data[j]) {
            copy[indexCopy--] = data[i--];
            count += j - start - length;
        } else {
            copy[indexCopy--] = data[j--];
        }
    }
    
    for (; i >= start; --i) {
        copy[indexCopy--] = data[i--];
    }
    
    for (; j >= start + length + 1; --j) {
        copy[indexCopy--] = data[j--];
    }
    
    return left + right + count;
}

int inversePairs(int *data, int length) {
    if (!data || length < 0) {
        return 0;
    }
    
    int *copy = new int[length];
    for (int i = 0; i < length; ++i) {
        copy[i] = data[i];
    }
    
    int count = inversePairsCore(data, copy, 0, length - 1);
    delete [] copy;
    
    return count;
}

